/*
class Solution {
 public:
  vector<int> path;
  vector<vector<int>> ans;
  vector<vector<int>> pathSum(TreeNode* root, int target) {
    recur(root, target);
    return ans;
  }
  void recur(TreeNode* root, int target) {
    if (!root) return;
    if (!root->left && !root->right && target == root->val) {
      path.push_back(root->val);
      ans.push_back(path);
      path.pop_back();
    }
    path.push_back(root->val);
    recur(root->left, target - root->val);
    recur(root->right, target - root->val);
    path.pop_back();
  }
};
*/
class Solution {
 public:
  vector<int> path;
  vector<vector<int>> ans;
  vector<vector<int>> pathSum(TreeNode* root, int target) {
    if (root) recur(root, target - root->val);
    return ans;
  }
  void recur(TreeNode* root, int target) {
    if (!root) return;
    if (!root->left && !root->right && target == 0) {
      path.push_back(root->val);
      ans.push_back(path);
      path.pop_back();
    }
    path.push_back(root->val);
    if (root->left) {
      recur(root->left, target - root->left->val);
    }
    if (root->right) {
      recur(root->right, target - root->right->val);
    }
    path.pop_back();
  }
};